//LCP 28.采购方案
//https://leetcode.cn/problems/4xy4Wx/
class Solution {
public:
    int purchasePlans(vector<int>& nums, int target) {
        //排序后找区间内有多少个满足的方法
        // 1 2 3 4 5 target=6  1-5区间中有 1-2 1-3 1-4 1-5 可以组成 所以是4
        // 然后从1->2 开始遍历 2-5太大了 5->4
        // 2-4满足 3-4不满足 4->3 1
        //2-3满足 1
        //3-3遍历结束
        long long ret = 0;
        const long long mod = 1000000007;
        sort(nums.begin(),nums.end());
        int l = 0,r = nums.size()-1;
        while(l < r)
        {
            //找到合适的右区间
            while(l<r && nums[l]+nums[r]>target) --r;
            ret += r-l;
            ++l;
        }
        return ret%mod;
    }
};